package main

import "sort"

func main() {
	// [1. 两数之和](https://leetcode.cn/problems/two-sum/)
	// [454. 四数相加 II](https://leetcode.cn/problems/4sum-ii/)
	// [383. 赎金信](https://leetcode.cn/problems/ransom-note/)
	// [15. 三数之和](https://leetcode.cn/problems/3sum/)
	// [18. 四数之和](https://leetcode.cn/problems/4sum/)
}

// 1
func twoSum(nums []int, target int) []int {
	mp := make(map[int]int)
	for idx1, v := range nums {
		key := target - v
		if idx2, ok := mp[key]; ok {
			return []int{idx1, idx2}
		} else {
			mp[v] = idx1
		}
	}
	return []int{0, 0}
}

// 454
func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
	m1 := make(map[int]int)
	for _, v1 := range nums1 {
		for _, v2 := range nums2 {
			m1[v1+v2]++
		}
	}
	ans := 0
	for _, v1 := range nums3 {
		for _, v2 := range nums4 {
			if _, ok := m1[0-(v1+v2)]; ok {
				ans += m1[0-(v1+v2)]
			}
		}
	}
	return ans
}

// 383
func canConstruct(ransomNote string, magazine string) bool {
	m1 := make(map[byte]int)
	for _, v := range magazine {
		m1[byte(v)]++
	}
	for _, k := range ransomNote {
		m1[byte(k)]--
		if m1[byte(k)] < 0 {
			return false
		}
	}
	return true
}

// 15
func threeSum(nums []int) [][]int {
	//固定a，枚举b、c
	sort.Ints(nums)
	ans := make([][]int, 0)
	for i := range nums {
		//去重a
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		//固定a
		a := nums[i]
		//枚举b、c
		l, r := i+1, len(nums)-1
		for l < r {
			b, c := nums[l], nums[r]
			cnt := a + b + c
			if cnt > 0 {
				r--
			} else if cnt < 0 {
				l++
			} else {
				ans = append(ans, []int{a, b, c})
				//去重b
				for l < r && nums[l] == nums[l+1] {
					l++
				}
				//去重c
				for l < r && nums[r] == nums[r-1] {
					r--
				}
				//进行下一位置枚举
				r--
				l++
			}
		}
	}
	return ans
}

// 18
func fourSum(nums []int, target int) [][]int {
	//[-2, -1, 0, 0, 2]
	sort.Ints(nums)
	ans := make([][]int, 0)
	n := len(nums)
	for i := 0; i < n-3; i++ {
		a := nums[i]
		for j := i + 1; j < n-2; j++ {
			b := nums[j]
			//枚举c、d
			l, r := j+1, n-1
			for l < r {
				c, d := nums[l], nums[r]
				cnt := a + b + c + d
				if cnt > target {
					r--
				} else if cnt < target {
					l++
				} else {
					ans = append(ans, []int{a, b, c, d})
					//去重c
					for l < r && nums[l] == nums[l+1] {
						l++
					}
					//去重d
					for l < r && nums[r] == nums[r-1] {
						r--
					}
					//进行下次递归
					l++
					r--
				}
			}
			//去重
			for j < n-2 && nums[j] == nums[j+1] {
				j++
			}
		}
		//去重
		for i < n-3 && nums[i] == nums[i+1] {
			i++
		}
	}
	return ans
}
